Zadanie Eulera
Limit pamięci: 128 MB
Leonhard Euler (1707-1783) wielkim matematykiem był.
W tym zadaniu rozważymy jedną z funkcji nazwanych na jego cześć, a mianowicie funkcję
Eulera.
Wartością funkcji
dla liczby naturalnej
jest liczba liczb
(
)
względnie pierwszych z
. Dwie liczby są względnie pierwsze, jeśli nie mają
wspólnego dzielnika większego niż 1. Na przykład
, gdyż liczby 1 oraz 5 są względnie
pierwsze z liczbą 6, natomiast liczby 2, 3, 4 i 6 nie są.
Zadanie, które mógłby zadać Euler, gdyby nadal żył, mogłoby być następujące: dla ustalonej
liczby naturalnej
znajdź wszystkie liczby naturalne
, które spełniają równanie
Wejście
W pierwszym wierszu wejścia znajduje się jedna liczba naturalna
(
) określająca
liczbę zestawów danych. W kolejnych
wierszach znajdują się opisy kolejnych zestawów danych.
Każdy opis zawiera jedną liczbę naturalną
(
).
Wyjście
Twój program powinien wypisać na wyjście odpowiedzi dla poszczególnych zestawów danych w kolejności ich
występowania na wejściu. Odpowiedź dla zestawu składa się z dwóch wierszy. W pierwszym wierszu
powinna się znaleźć liczba rozwiązań. W drugim wierszu powinny się znaleźć wszystkie rozwiązania
równania podane w kolejności rosnącej. Jeśli równanie nie ma
rozwiązań, to drugi wiersz odpowiedzi dla zestawu danych powinien pozostać pusty.
Przykład
Dla danych wejściowych:
4
8
10
13
6
poprawną odpowiedzią jest:
5
15 16 20 24 30
2
11 22
0
4
7 9 14 18